package offer.day32;

public class No53Third_GetNumberSameAsIndex {
    /*
     * 面试题53：在排序数组中查找数字
     * 题目三：数组中数值和下表相等的元素
     * 假设一个单调递增的数组里的每一个元素都是整数并且是唯一的。
     * 请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。
     * 例如：在数组{-3,-1,1,3,5}中，数字3它的下标相等。
     *
     * 思路：同样运用二分查询的算法进行查找
     * 取中间值m和下标i进行比较：
     * 若m>i,数字大于下标，则可能相等的数字 在左侧
     * 若m<i,数字小于下标，则可能相等的数字 在右侧
     * 若m==i,找到数字与下标相等
     *
     * */
    public static void main(String[] args) {
        No53Third_GetNumberSameAsIndex g = new No53Third_GetNumberSameAsIndex();
        int[] array = {-3,-1,1,3,5};
        //其中下标是从0~n-1，并且返回的是下标值  ********
        System.out.println("数组中数字和其下表相等的位置是："+g.GetNumberSameAsIndex(array));
    }

    private int GetNumberSameAsIndex(int[] array) {
        if(array==null||array.length==0){
            return -1;
        }
        int left=0;
        int right=array.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(mid==array[mid]){
                return mid;
            }else if(mid<array[mid]){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return -1;

    }
}
